package Offer;

/**
 * 二叉搜索树的最近公共祖先
 * @author 是阿秋啊
 * @date 2022/04/17 17:56
 **/
public class Num68 {
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      //   方法一：普通二叉树公共祖先
        findNode(root,p,q);
        return lca;
        // 方法二： 非递归
//        while ((root.val - p.val) * (root.val - q.val) > 0) {
//            root = root.val - p.val > 0 ? root.left : root.right;
//        }
//        return root;
        // 方法三：递归
//        if ((root.val - p.val) * (root.val - q.val) <= 0) {
//            return root;
//        }
//        return lowestCommonAncestor(root.val - p.val > 0 ? root.left : root.right,p ,q);
    }

    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        int left = findNode(root.left,p,q) ? 1 : 0;
        int right = findNode(root.right,p,q) ? 1 : 0;
        int mid = ( root == p || root == q ) ? 1 : 0;
        if (left + right + mid == 2) {
            // 所有节点值唯一，所以不用考虑别的情况
            lca = root;
        }
        return left + right + mid > 0;
    }
}
